#include <bits/stdc++.h>

using namespace std;

// 子数组的最小值之和
// 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
// 由于答案可能很大，因此 返回答案模 10^9 + 7
// 测试链接 : https://leetcode.cn/problems/sum-of-subarray-minimums/

class Solution 
{
    const int MOD = 1e9 + 7;
    static const int MAXN = 30001;
    int st[MAXN], r;

public:
    int sumSubarrayMins(vector<int>& arr) 
    {
        int n = arr.size();
        long ans = 0;
        r = 0;
        for(int i = 0; i < n; ++i)
        {
            // i -> arr[i]
            // 避免计算重复的子数组
            while(r > 0 && arr[st[r - 1]] >= arr[i])
            {
                int cur = st[--r];
                int left = r > 0 ? st[r - 1] : -1;
                ans = (ans + (long)(cur - left) * (i - cur) * arr[cur]) % MOD;
            }
            st[r++] = i;
        }
        while(r > 0)
        {
            int cur = st[--r];
            int left = r > 0 ? st[r - 1] : -1;
            ans = (ans + (long)(cur - left) * (n - cur) * arr[cur]) % MOD;
        }
        return ans;
    }
};


class Solution 
{
    const int MOD = 1e9 + 7;

public:
    int sumSubarrayMins(vector<int>& arr) 
    {
        int n = arr.size();
        vector<int> left(n, -1);
        vector<int> right(n, n);
        stack<int> st;
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && arr[st.top()] >= arr[i])
            {
                right[st.top()] = i;
                st.pop(); 
            }
            if(!st.empty()) left[i] = st.top();
            st.push(i);
        }

        long long ret = 0;
        for(int i = 0; i < n; ++i)
        {
            ret = (ret + (long long)(i - left[i]) * (right[i] - i) * arr[i]) % MOD;
        }
        return ret % MOD;
    }
};